package com.tsx.leetcode.hot100.medium;

/**
 * <a href="https://leetcode.cn/problems/longest-palindromic-substring">最长回文子串</a>
 */
public class Q5LongestPalindrome {
    public static void main(String[] args) {
        Q5LongestPalindrome q5LongestPalindrome = new Q5LongestPalindrome();
        String s = "babad";
        String s1 = q5LongestPalindrome.longestPalindrome2(s);
        System.out.println("s1 = " + s1);
    }

    public String longestPalindrome1(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }
        int strlen = s.length();
        int left = 0;
        int right = 0;
        int len = 1;
        int maxStart = 0;
        int maxLen = 0;
        for (int i = 0; i < strlen; i++) {
            left = i - 1;
            right = i + 1;
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                len++;
                left--;
            }
            while (right < strlen && s.charAt(right) == s.charAt(i)) {
                len++;
                right++;
            }
            while (left >= 0 && right < strlen && s.charAt(right) == s.charAt(left)) {
                len = len + 2;
                left--;
                right++;
            }
            if (len > maxLen) {
                maxLen = len;
                maxStart = left;
            }
            len = 1;
        }
        return s.substring(maxStart + 1, maxStart + maxLen + 1);
    }

    public String longestPalindrome2(String s) {
        int n = s.length();
        int maxStart = 0;
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            // j = 0 表示中心节点只有 i，即回文串中心是单个字符；
            // j = 1 表示中心节点有两个 i 和 i + 1，即回文串中心是两个字符
            for (int j = 0; j <= 1; j++) {
                // 左指针，初始指向中心位置
                int l = i;
                // 右指针，根据 j 的值确定初始位置
                int r = i + j;
                // 当左右指针在字符串范围内且对应字符相等时，继续向两边扩展
                while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                    l--;
                    r++;
                }
                // 回溯到回文字符串的起始和结束位置
                // 因为上面的 while 循环结束时，l 和 r 已经越界了，所以要回退一步
                l++;
                r--;
                // 比较当前找到的回文子串长度和之前记录的最长回文子串长度
                if (maxLength < r - l + 1) {
                    maxLength = r - l + 1;
                    maxStart = l;
                }
            }
        }
        return s.substring(maxStart, maxStart + maxLength);
    }

    public String longestPalindrome(String s) {
        int sLen = s.length();
        int maxLen = 0;
        String ans = "";
        boolean[][] P = new boolean[sLen][sLen];
        // 遍历所有长度
        for (int len = 1; len <= sLen; len++) {
            for (int start = 0; start < sLen; start++) {
                int end = start + len - 1;
                // 下标越界，结束循环
                if (end >= sLen) {
                    break;
                }
                P[start][end] = (len == 1 || len == 2 || P[start + 1][end - 1])
                        && s.charAt(start) == s.charAt(end);
                if (P[start][end] && len > maxLen) {
                    maxLen = len;
                    ans = s.substring(start, end + 1);
                }
            }
        }
        return ans;
    }
}
